\section{The pointer chasing problem} \label{sec:pointer_chasing}

%We prove Theorem~\ref{thm:rw_lower_bound} by reducing from the communication complexity of the {\em Pointer Chasing Problem}, defined as follows.

In this section, we define the pointer chasing problem and prove its lower bound (Lemma~\ref{lem:PC_dist_lowerbound}) which will be used to prove Theorem~\ref{thm:rw_lower_bound} in the next section.

Informally, the $r$-round pointer chasing problem has parameters $r$ and $m$ and there are two players, which could be Alice and Bob or nodes $s$ and $t$, who receive functions $f_A:[m]\rightarrow[m]$ and $f_B:[m]\rightarrow[m]$, respectively. The goal is to compute a function starting from $1$ and alternatively applying $f_A$ and $f_B$ for $r$ times each, i.e., compute $f_B(\ldots f_A(f_B(f_A)))$ where $f_A$ and $f_B$ appear $r$ times each.
%
To be precise, let $\cF_m$ be the set of functions $f:[m]\rightarrow [m]$. For any $i\geq 0$ define $g^{i}: \cF_m\times\cF_m\rightarrow [m]$ inductively as
\[g^{0}(f_A, f_B)=1  ~~~\mbox{and}~~~\]
% 
\[g^{i}(f_A, f_B)\begin{cases}
f_A(g^{i-1}(f_A, f_B)) & \mbox{if $i>0$ and $i$ is odd,}\\
f_B(g^{i-1}(f_A, f_B)) & \mbox{if $i>0$ and $i$ is even.}
\end{cases}\]
%
Also define function $\PC^{i, m}(f_A, f_B)=g^{2i}(f_A, f_B)$. The goal of the $r$-round pointer chasing problem is to compute $\PC^{r, m}(f_A, f_B)$.

%We consider a variant of this problem where Alice and Bob receive $d$ pairs of functions $(f^1_A, f^1_B)$, $\ldots$, $(f^d_A, f^d_B)$ and want to output $d$ values resulting from chasing these pairs of functions for $r$ rounds each. We denote this problem by $\PC^{r, m, d}$.\danupon{Should we provide a formal definition?}

Observe that if Alice and Bob can communicate for $r$ rounds then they can compute $\PC^{r, m}$ naively by exchanging $O(r\log m)$ bits. Interestingly, Nisan and Wigderson~\cite{NisanW93} show that if Alice and Bob are allowed only $r-1$ rounds then they essentially cannot do anything better than having Alice sent everything she knows to Bob.\footnote{In fact this holds even when Alice and Bob are allowed $r$ rounds but Alice cannot send a message in the first round.}

%The following result is due to Jain, Radhakrishnan, and Sen~\cite{JainRS03}\footnote{In fact this holds even when Alice and Bob are allowed $r$ rounds but Bob has to speak first.}.\danupon{Question: Is there a version where there is one function but we have to start from k different places? If there is then we can improve $n$ a bit.}

%We can use the version where there are $d$ functions and we have to chase a pointer for each function. The lower bound is $\Omega(dm/r^3-dr\log m-2r)$ (JainRS ICALP03~\cite{JainRS03}) where $r$ is the number of rounds.\danupon{Question: Is there a version where there is one function but we have to start from k different places?}
%
%\begin{theorem}\cite{JainRS03}\label{thm:pointer_chasing}
%$R^{(r-1)-cc-pub}_{1/3}(\PC^{r, m, d})=\Omega(dmr^{-3}-dr\log m-2d)$.
%\end{theorem}


\begin{theorem}\cite{NisanW93}\label{thm:pointer_chasing}
$R^{(r-1)-cc-pub}_{1/3}(\PC^{r, m})=\Omega(m/r^{2}-r\log m)$.
\end{theorem}

\paragraph{The pointer chasing problem on $\graph$.} We now consider the pointer chasing problem on network $\graph$ where $s$ and $t$ receive $f_A$ and $f_B$ respectively. The following lemma follows from Theorem~\ref{thm:cc_to_distributed} and \ref{thm:pointer_chasing}.
%We first show a lower bound of the pointer chasing problem on network $G\in \graph$, for any $\Gamma$. The following claim follows from Theorem~\ref{thm:cc_to_distributed} and \ref{thm:pointer_chasing}.
%
%
\begin{lemma}\label{lem:PC_dist_lowerbound}
For any $\kappa$, $\Gamma$, $\Lambda\geq 2$, $m\geq \kappa^2\Lambda^{4\kappa}\log n$, $16\Lambda^{\kappa-1}\geq r>8\Lambda^{\kappa-1}$, $R^{\graph, s, t}_{1/3}(\PC^{r, m})=\Omega(\kappa\Lambda^{\kappa})$.
\end{lemma}
% This is a shorter proof.
%\begin{proof}[Short Proof]
%If $R_{1/3}^{\graph, s, t}(\PC^{r, m, d})\leq \kappa\Lambda^\kappa$ then
%%
%\begin{align*}
%R_{1/3}^{\graph, s, t}(\PC^{r, m})&\geq R_{1/3}^{\frac{8R_{1/3}^{\graph, s, t}(\PC^{r, m})}{\kappa\Lambda}-cc-pub}(\PC^{r, m})/(2B) &&\mbox{(by Theorem~\ref{thm:cc_to_distributed})}\\
%&\geq R_{1/3}^{\frac{8\kappa\Lambda^\kappa}{\kappa\Lambda}-cc-pub}(\PC^{r, m})/(2B) &&\mbox{(allow max number of rounds)}\\
%&= \Omega((m(8\Lambda^{\kappa-1})^{-2}-8\Lambda^{\kappa-1}\log m)/B) &&\mbox{(by Theorem~\ref{thm:pointer_chasing} with $r>8\kappa\Lambda^{\kappa-1}$)} \\
%%&= \Omega(d+T^2) &&\mbox{(since $m\geq4\Lambda^{5\kappa}\geq 4T^5$)}\\
%&= \Omega(\kappa\Lambda^{\kappa}) &&\mbox{(since $m\geq4B\kappa\Lambda^{4\kappa}$)}\,.
%\end{align*}
%The lemma follows.
%\end{proof}

\begin{proof}%[Long Proof]\danupon{To be in Appendix.}
%If $R_{1/3}^{\graph, s, t}(\PC^{r, m})> \kappa\Lambda^\kappa$ then we are done so we assume that $R_{1/3}^{\graph, s, t}(\PC^{r, m})\leq \kappa\Lambda^\kappa$. Thus,
%
Let $r=R_{1/3}^{\graph, s, t}(\PC^{r, m})$. If $r> \kappa\Lambda^\kappa$ then we are done so we assume that $r \leq \kappa\Lambda^\kappa$. Thus,
%
\begin{align}
r&\geq \frac{R_{1/3}^{\frac{8R_{1/3}^{\graph, s, t}(\PC^{r, m})}{\kappa\Lambda}-cc-pub}(\PC^{r, m})}{(2\kappa\log n)} \label{eq:a}\\
&\geq \frac{R_{1/3}^{\frac{8\kappa\Lambda^\kappa}{\kappa\Lambda}-cc-pub}(\PC^{r, m})}{(2\kappa\log n)}\label{eq:b} \\
&= \Omega(\frac{(m(8\Lambda^{\kappa-1})^{-2}-8\Lambda^{\kappa-1}\log m)}{(\kappa\log n)}) \label{eq:c} \\
&= \Omega(\kappa\Lambda^{\kappa}) \label{eq:d}
\end{align}
where Eq.~\eqref{eq:a} is by Theorem~\ref{thm:cc_to_distributed} and the fact that $r\leq \kappa\Lambda^\kappa$, Eq.~\eqref{eq:b} uses the fact that the communication does not increase when we allow more rounds and $R_{1/3}^{\graph, s, t}(\PC^{r, m})\leq \kappa\Lambda^\kappa$, Eq.~\eqref{eq:c} follows from Theorem~\ref{thm:pointer_chasing} with the fact that $16\Lambda^{\kappa-1}\geq r>8\Lambda^{\kappa-1}$ and Eq.~\eqref{eq:d} is because $m\geq \kappa^2\Lambda^{4\kappa}\log n$.
%
%
%In this case, conditions in Theorem~\ref{thm:cc_to_distributed} hold. Thus,
%%
%\begin{align}
%R_{1/3}^{\graph, s, t}(\PC^{r, m})&\geq R_{1/3}^{\frac{8R_{1/3}^{\graph, s, t}(\PC^{r, m})}{\kappa\Lambda}-cc-pub}(\PC^{r, m})/(2B)\label{eq:a}
%\end{align}
%%
%Since the communication does not increase when we increase the number of rounds, the right hand side of Eq.~\eqref{eq:a} is
%\begin{align}
%&\geq R_{1/3}^{\frac{8\kappa\Lambda^\kappa}{\kappa\Lambda}-cc-pub}(\PC^{r, m})/(2B)\,. \label{eq:b}
%\end{align}
%Since $r>8\kappa\Lambda^{\kappa-1}$, Theorem~\ref{thm:pointer_chasing} implies that the right hand side of Eq.~\ref{eq:b} is
%\begin{align}
%&= \Omega((m(8\Lambda^{\kappa-1})^{-2}-8\Lambda^{\kappa-1}\log m)/B)\label{eq:c}\,.
%\end{align}
%Using $m\geq4B\kappa\Lambda^{4\kappa}$, the right hand side of Eq.~\eqref{eq:c} is
%\begin{align*}
%&= \Omega(\kappa\Lambda^{\kappa})\,.
%\end{align*}
%
%The lemma follows.
\end{proof}
